/**
 * Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 */
package com.xinpan.exercise;

	import java.util.ArrayList;
	import java.util.Comparator;
	import java.util.PriorityQueue;

public class MergeKSortedList {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // Start typing your Java solution below
        // DO NOT write main() function
    	if(lists.size() == 0)
    		return null;
    	
        PriorityQueue<ListNode> sList = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(){

			@Override
			public int compare(ListNode o1, ListNode o2) {
				// TODO Auto-generated method stub
				return o1.val > o2.val ? 1 : (o1.val < o2.val ? -1 : 0);
			}
        });
        
        for(ListNode aNode : lists)
        {
            if(aNode != null)
                sList.add(aNode);
        }
        
        ListNode head = null;
        ListNode cur = null;
        while(sList.size() > 0)
        {
        	ListNode aNode = sList.poll();
        	ListNode nNode = aNode.next;
        	if(nNode != null)
        	{
        		sList.add(nNode);
        		aNode.next = null;
        	}
        	
        	if(head == null)
        	{
        		head = aNode;
        		cur = head;
        	}
        	else
        	{
        		cur.next = aNode;
        		cur = cur.next;
        	}
        }
        
        return head;
        
    }
    class ListNode {
    	      int val;
    	      ListNode next;
    	      ListNode(int x) {
    	          val = x;
    	          next = null;
    	      }
    }
    
    public static void main(String[] args)
    {
    	 MergeKSortedList msl = new  MergeKSortedList();
    	 ArrayList<ListNode> list = new ArrayList<ListNode>();
    	 msl.mergeKLists(new ArrayList<ListNode>());
    }
}
